package algorithm.difficult;

import jdk.nashorn.internal.ir.IfNode;

import java.util.*;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.difficult
 * @Author: 江岸
 * @CreateTime: 2021-03-04 19:56
 * @Description: 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 *
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 *
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 *
 * 注意：不允许旋转信封。
 *
 *
 * 示例 1：
 *
 * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
 *
 * 示例 2：
 *
 * 输入：envelopes = [[1,1],[1,1],[1,1]]
 * 输出：1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/russian-doll-envelopes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxEnvelopes354 {
    public static void main(String[] args) {
        int[][] arr = {{5,4},{6,4},{6,7},{2,3}};
        maxEnvelopes(arr);
    }
    //二维数组 动态规划 二分查找
    public static int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length<=1){
            return envelopes.length;
        }
        /**
         * 我们可以将 h 值作为排序的第二关键字进行降序排序，这样一来，对于每一种 w 值，
         * 其对应的信封在排序后的数组中是按照 h 值递减的顺序出现的，
         * h 值不可能组成长度超过 1 的严格递增的序列，这就从根本上杜绝了错误的出现。
         * 因此我们就可以得到解决本题需要的方法：
         * 首先我们将所有的信封按照 w 值第一关键字升序、h 值第二关键字降序进行排序；
         *  随后我们就可以忽略 w 维度，求出 h 维度的最长严格递增子序列，其长度即为答案。
         */
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) {
                    return e1[0] - e2[0];
                } else {
                    return e2[1] - e1[1];
                }
            }
        });
        List<Integer> f = new ArrayList<Integer>();
        for (int i=0;i<envelopes.length;i++){
                f.add(envelopes[i][1]);
        }
        System.out.println(f);
        int[] tail = new int[f.size()];
        int end = 0;
        tail[0] = f.get(0);
        end++;
        for (int i=1;i<f.size();i++){
            if (f.get(i)>tail[end-1]){
                //当前数大于tail末尾数，直接往后添加
                tail[end] = f.get(i);
                end++;
            }else {
                //二分查找 找到一个刚好大于nums[i]的数
                int left = 0;
                int right = end;
                int mid;
                while (left<right){
                    mid = left + ((right-left)>>>1);
                    if (tail[mid]<f.get(i)){
                        left = mid+1;
                    }else {
                        right = mid;
                    }
                }
                tail[left] = f.get(i);
            }
        }
        return end;
    }


}
